﻿// RopeNode.cs
//
// Author: 
//          Luoyingliang <731984870@qq.com>
// 
// Copyright (c) 2018 Team Acoris
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.


using System;
using System.Diagnostics;
using System.Text;

namespace Acoris.Text
{
    /// <summary>
    /// represents a node of Rope
    /// </summary>
    public sealed class RopeNode
    {
        private const string ArrayNull = "array cannot be null";
        private const string NodeNull = "node cannot be null";
        private const string IndexNegativeValue = "index cannot be a negative value";
        private const string CountTooLarge="invalidate value,please check the length of array";


        public const int MaxSize = 256;
        public static readonly RopeNode EmptyNode = new RopeNode{ height = 0 , shared = true };


        internal RopeNode left;
        internal RopeNode right;
        internal byte height;
        internal int length;
        internal char[] contents;
        internal volatile bool shared;

        internal int Balance {
            get {
                return left.height - right.height;
            }
        }

        #region CreateFromArray / CreateFromString

        internal static RopeNode CreateFromArray(char[] array, int index, int count) {
            Debug.Assert(array != null, "array can't be null");
            Debug.Assert(array.Length != 0, "array can't be empty");
            Debug.Assert(array.Length >= index + count, "index out of range");

            var leafCount = (count + 255)/MaxSize;
            var result = CreateNodes(leafCount,count);

            // set content to rope node
            result.SetContents(0, array, index, count);
            return result;

        }

        internal static RopeNode CreateFromString(string text) {
            var array = text.ToCharArray();
            return CreateFromArray(array, 0, array.Length);
        }


        private static RopeNode CreateNodes(int leafCount, int totalCount) {

            var result = (RopeNode)null;

            // recusive create node
            // 

            if (leafCount == 1) {
                result = new RopeNode { height = 0, length = totalCount,contents = new char[MaxSize] };
            }
            else {
                var leftLeafCount = leafCount / 2;
                var leftCount = leftLeafCount * 2;

                var left = CreateNodes(leftLeafCount, leftCount);
                var right = CreateNodes(leafCount - leftLeafCount, totalCount - leftCount);
                result = new RopeNode
                {
                    left = left,
                    right = right,
                    height = (byte)(1 + Math.Max(left.height, right.height))
                };
            }
            return result;
        }
        #endregion

        /// <summary>
        /// concatenate the specific nodes
        /// </summary>
        /// <param name="left">the left node</param>
        /// <param name="right">the right node</param>
        /// <returns>
        /// return a new node after concatenate operation
        /// </returns>
        public static RopeNode Concat(RopeNode left, RopeNode right) {

            if (left == null || left.length == 0) {
                return right;
            }

            if (right == null || right.length == 0) {
                return left;
            }


            if (RopeNode.MaxSize >= left.length + right.length) {
                // for all node which less than RopeNode.MaxSize
                // we considering merge them

                left.SetContents(left.length, right.contents, 0, right.length);
                left.length += right.length;
                left.height = (byte)(1 + Math.Max(left.height, right.height));
                left.Publish();
                return left;

            }
            else {
                var result = new RopeNode
                {
                    left = left,
                    right = right,
                    height = (byte)( 1+ Math.Max(left.height,right.height)),
                    shared = false
                };
                result.Rebalance();
                return result;
            }
        }

        /// <summary>
        /// insert element to the specific node
        /// </summary>
        /// <param name="node">insert operation's destination node</param>
        /// <param name="offset">insert position</param>
        /// <param name="array">source array</param>
        /// <param name="arrayIndex">source array index</param>
        /// <param name="count">insert count</param>
        /// <returns>return a new node after insert</returns>
        public static RopeNode InsertRange(RopeNode node, int offset, char[] array, int arrayIndex, int count) {
            Debug.Assert(offset > -1 && arrayIndex > -1, "index cannot be a negative value");
            Debug.Assert(array != null, ArrayNull);

            var element = CreateFromArray(array,arrayIndex,count);
            return Insert(node, offset, element);
        }

        /// <summary>
        /// insert element to the specific node
        /// </summary>
        /// <param name="node">insert operation's destination node</param>
        /// <param name="offset">insert position</param>
        /// <param name="element">new element</param>
        /// <returns>return a new node after insert</returns>
        public static RopeNode Insert(RopeNode node, int offset, RopeNode element) {

            Debug.Assert(offset > -1, IndexNegativeValue);
            Debug.Assert(element != null, NodeNull);

            if (offset == 0) {
                return Concat(node, element);
            }

            if (offset == node.length) {
                return Concat(element, node);
            }

            if (node.height == 0) {
                var before = node;
                var after = node.Split(offset);
                return Concat(before, Concat(after, element));
            }
            else {

                if (offset < node.left.length) {
                    return Insert(node.left, offset, element);
                }
                else {
                    return Insert(node.right, offset - node.left.length, element);
                }
            }
        }

        /// <summary>
        /// gets a string which reprensents this object
        /// </summary>
        /// <returns>return a string which reprensents this object</returns>
        public override string ToString() {
            if (height == 0) {
                return $"length:{length}";
            }

            return $"height:{height},length:{length}";
        }
    }

    // remember the rope data-structure should take more attention
    // to reducing the node amount and memeory usage
    // and evaluate merge operation in possible situation
    //
    // 

    /// <summary>
    /// represents RopeNode class extension methods
    /// </summary>
    public static class RopeNodeExtension
    {
        private const string ArrayNull = "array cannot be null";
        private const string NodeNull = "node cannot be null";
        private const string IndexNegativeValue = "index cannot be a negative value";
        private const string CountTooLarge="invalidate value,please check the length of array";

        /// <summary>
        /// copy datas from node to array
        /// </summary>
        /// <param name="node">source node</param>
        /// <param name="array">destination array</param>
        /// <param name="index">destination index</param>
        /// <param name="count">destination count</param>
        public static void CopyTo(this RopeNode node, char[] array, int index, int count) {
            Debug.Assert(array != null, ArrayNull);
            Debug.Assert(index > -1, IndexNegativeValue);
            Debug.Assert(count <= node.length, CountTooLarge);

            Array.Copy(node.contents, 0, array, index, count);
        }

        /// <summary>
        /// set contents to node
        /// </summary>
        /// <param name="node">source node</param>
        /// <param name="index">the index in node</param>
        /// <param name="array">destination array</param>
        /// <param name="arrayIndex">the index in destination array</param>
        /// <param name="count">count</param>
        public static void SetContents(this RopeNode node, int index, char[] array, int arrayIndex, int count) {

            // this method should not be modify the length field in rope node
            // we modified the length field only in merge、concat、split
            // and create nodes operations

            Debug.Assert(index > -1 && arrayIndex > -1, IndexNegativeValue);
            Debug.Assert(array != null, ArrayNull);
            //Debug.Assert((node.length - index) < count, CountTooLarge);

            if (node.height == 0) {

                Array.Copy(array, arrayIndex, node.contents, index, count);
            }
            else {

                var left = node.left;
                var right = node.right;

                left.SetContents(index, array, 0, left.length);
                right.SetContents(index, array, left.length, count - left.length);

            }

        }

        /// <summary>
        /// append content to StringBuilder
        /// </summary>
        /// <param name="node">source node</param>
        /// <param name="stringBuilder">StringBuilder</param>
        /// <param name="offset">start position</param>
        /// <param name="count">count</param>
        /// <returns>return the newest StringBuilder instance</returns>
        public static StringBuilder AppendString(this RopeNode node,StringBuilder stringBuilder,int offset,int count) {

            Debug.Assert(offset > -1, IndexNegativeValue);
            Debug.Assert(count + offset < node.length, CountTooLarge);

            stringBuilder.Append(node.contents, offset, count);

            return stringBuilder;
        }

        /// <summary>
        /// clone or return source node
        /// </summary>
        /// <param name="node">source node</param>
        /// <returns>this method will return a new node or source node</returns>
        public static RopeNode Clone(this RopeNode node) {
            if (node.shared) {

                if (node.height == 0) {
                    // if source node's height was zero 
                    // that means this node is leaf node
                    // we should copy the content and return it
                    var newContents = new char[RopeNode.MaxSize];
                    node.CopyTo(newContents, 0, node.length);

                    return new RopeNode
                    {
                        height = 0,
                        shared = false,
                        contents = newContents,
                        length = node.length,
                    };
                }
                else {
                    // just return a new concat node
                    return new RopeNode
                    {
                        height = node.height,
                        length = node.length,
                        left = node.left,
                        right = node.right,
                        shared = false,
                        contents = null
                    };
                }

            }
            else {
                // if source node was unshared and return this
                return node;
            }
        }

        /// <summary>
        /// change the specific node's share state
        /// </summary>
        /// <param name="node"></param>
        public static void Publish(this RopeNode node) {
            if (node.left != null) {
                node.left.Publish();
            }

            if (node.right != null) {
                node.right.Publish();
            }

            node.shared = true;
        }

        /// <summary>
        /// concatenate the specific nodes
        /// </summary>
        /// <param name="left">the left node</param>
        /// <param name="right">the right node</param>
        /// <returns>
        /// return a new node after concatenate operation
        /// </returns>
        public static RopeNode Concat(this RopeNode left, RopeNode right) {

            if (left == null) {
                return right;
            }

            if (right == null) {
                return left;
            }


            if (RopeNode.MaxSize >= left.length + right.length) {
                // for all node which less than RopeNode.MaxSize
                // we considering merge them

                left.SetContents(left.length, right.contents, 0, right.length);
                left.length += right.length;
                left.Publish();
                return left;

            }
            else {
                var result = new RopeNode
                {
                    left = left,
                    right = right,
                    height = (byte)( 1+ Math.Max(left.height,right.height)),
                    shared = false
                };
                result.Rebalance();
                return result;
            }
        }

        /// <summary>
        /// split source node in specific position,and return a new node after split
        /// </summary>
        /// <param name="node">source node</param>
        /// <param name="offset">split operation's destination position</param>
        /// <returns>return a new node after split</returns>
        public static RopeNode Split(this RopeNode node, int offset) {
            Debug.Assert(node.height == 0);
            // if the offset equal zero that means we should 
            // return this node as split after
            if (offset == 0) {
                return node.Clone();
            }

            var newContents = new char[RopeNode.MaxSize];
            var length = node.length - offset;
            node.CopyTo(newContents, offset, length);

            var result = new RopeNode
            {
                height = 0,
                shared = false,
                contents = newContents,
                length = length,

            };
            node.length = offset;

            return result;
        }

        /// <summary>
        /// remove specific range from node
        /// </summary>
        /// <param name="node">source node</param>
        /// <param name="offset">remove position</param>
        /// <param name="count">remove count</param>
        /// <returns>return a new node after remove</returns>
        public static RopeNode RemoveRange(this RopeNode node, int offset, int count) {

            Debug.Assert(offset > -1, IndexNegativeValue);
            Debug.Assert(node.length >= offset + count, CountTooLarge);

            if(offset == 0 && count == node.length) {
                return RopeNode.EmptyNode;
            }

            var result = (RopeNode)null;

            if(node.height == 0) {
                result = node.Clone();
                RemoveContent(result.contents,result.length, offset, count);
                result.length -= count;
            }
            else {
                var left = node.left;
                var right = node.right;

                if(offset < node.length) {
                    var removeCount = count - left.length;
                    result = left.RemoveRange(offset, count);

                    if(removeCount > 0) {
                        result = RopeNode.Concat(result,right.RemoveRange(0, removeCount));
                    }

                }
                else {
                    result = right.RemoveRange(offset - left.length, count);
                }
            }

            return result;

        }

        internal static void RemoveContent(char[] array,int length, int offset, int count) {
            var afterIndex = offset + count;
            var afterCount = length - count;
            Array.Copy(array, afterIndex, array, offset, afterCount);
        }


        /// <summary>
        /// start a rebalance operation,and keep this node's subtree is balanced
        /// </summary>
        /// <param name="rope">source node</param>
        public static void Rebalance(this RopeNode node) {

            if (node.height < 1) {
                return;
            }

            var left = node.left;
            var right = node.right;

            while (Math.Abs(node.Balance) > 1) {

                //  figure:
                //-------------------------------------------------
                //          node       |          node
                //        /            |        /      \     
                //      b              |        b        c
                //    /                |     /    \
                //  c                  |   d        e
                //                     |          /
                //                     |        f
                //        (1)                       (2)
                // as figure show,we should reducing this two type
                // 


                if (node.Balance > 1) {

                    if (left.height > 0 && left.Balance < 0) {
                        left.RotateToLeft();
                    }

                    node.RotateToRight();
                }
                else if (node.Balance < -1) {

                    if (right.height > 0 && right.Balance > 0) {
                        right.RotateToRight();
                    }

                    node.RotateToLeft();
                }
            }

            node.height = (byte)(1 + Math.Max(left.height, right.height));
        }

        /// <summary>
        /// check condition and merge specific node if it need
        /// </summary>
        /// <param name="node">source node</param>
        internal static void MergeIfPossible(this RopeNode node) {

            if (RopeNode.MaxSize >= node.length) {

                var left = node.left;
                var right = node.right;

                if (node.height == 1) {

                    var newContents = new char[RopeNode.MaxSize];

                    left.CopyTo(newContents, 0, left.length);

                    if (node.length - left.length > 0) {
                        right.CopyTo(newContents, left.length, right.length);
                    }

                    node.height = 0;
                    node.left = node.right = null;
                    node.contents = newContents;
                }
                else if (node.height > 1) {
                    left.MergeIfPossible();
                    right?.MergeIfPossible();
                }
            }
        }

        /// <summary>
        /// evaluate rotate operation,and rotate this subtree to left
        /// </summary>
        /// <param name="node">source node</param>
        internal static void RotateToLeft(this RopeNode node) {
            /* Rotate tree to the left
			 * 
			 *       this               this
			 *       /  \               /  \
			 *      A   right   ===>  left  C
			 *           / \          / \
			 *          B   C        A   B
			 */
            RopeNode a = node.left;
            RopeNode b = node.right.left;
            RopeNode c = node.right.right;

            var left = node.right.Clone();
            left.left = a;
            left.right = b;

            node.left = left;
            node.right = c;


            left.MergeIfPossible();
            node.height = (byte)(1 + Math.Max(left.height, c.height));
            node.Publish();

        }

        /// <summary>
        /// evaluate rotate operation,and rotate this subtree to right
        /// </summary>
        /// <param name="node">source node</param>
        internal static void RotateToRight(this RopeNode node) {
            /* Rotate tree to the right
			 * 
			 *       this             this
			 *       /  \             /  \
			 *     left  C   ===>    A  right
			 *     / \                   /  \
			 *    A   B                 B    C
			 */
            RopeNode a = node.left.left;
            RopeNode b = node.left.right;
            RopeNode c = node.right;
            RopeNode left = node.left.Clone();

            left.left = b;
            left.right = c;

            node.left = a;
            node.right = left;

            left.MergeIfPossible();
            node.height = (byte)(1 + Math.Max(a.height, left.height));
            node.Publish();

        }
    }
}

namespace Acoris.Test
{
    using Acoris.Text;

    /// <summary>
    /// represents a rope node test data generator
    /// </summary>
    public class RopeNodeTestHelper
    {
        #region Concat

        public static bool TestConcatCase1() {
            var left = new RopeNode{ length = 1};
            var right = RopeNode.EmptyNode;

            var result1 = RopeNode.Concat(left,right);
            var result2 = RopeNode.Concat(left,null);

            // TODO:

            return false;
        }

        #endregion
    }
}
